
/**
 * 
 */
package com.zsrt.day20170410;

import java.util.Arrays;

import org.junit.Test;

import com.zsrt.utils.ArrayUtil;

/**
 * 快速排序
 * @author jmj
 * @date 2017年4月10日
 * @time 上午10:11:29
 */
public class KuaiPai {
	@Test
	public void sortTest1() throws Exception {
		int[] array={23,45,54,22,13,87,62};
		ArrayUtil.quickSort(array, 0, array.length -1);
		ArrayUtil.printArray(array);
	}
	@Test
	public void sortTest2() throws Exception {
		int[] array={23,45,54,22,13,87,62};
		Arrays.sort(array);
		ArrayUtil.printArray(array);
	}
	
	@Test
	public void sortTest() throws Exception {
		int[] array={23,20,19,29,13,87,62};
		sort(array,0,array.length-1);
		ArrayUtil.printArray(array);	
	}
	public void sort(int[] arrays,int begin,int end){
		int i = begin;
		int j = end;
		
		if(begin>=end){
			//结束整个方法
			//System.out.println("结束方法。不用排序...");
			return;
		}
		
		int key = arrays[i];
		
		//打印begin和end
		//System.out.println("begin="+begin+"end="+end);
		//ArrayUtil.printArray(arrays);
		//System.out.println();
		
		
		while(true){
			//System.out.println("进入循环");
			//从右往左循环
			while(j>i){
				if(arrays[j]<key){
					ArrayUtil.changePosition(arrays, i,j);
					break;
				}else{
					j--;
				}
			}
			//从左往右循环
			while(i<j){
				if(arrays[i]>key){
					ArrayUtil.changePosition(arrays, i, j);
					break;
				}else{
					i++;
				}
			}
			
			//结束一趟循环
			if(i==j){
				break;
			}
			
		    
		}
		
		//System.out.println(i);
		//递归左边
		sort(arrays,begin,i-1);
		//递归右边
	    sort(arrays,i+1,end);
	}
   
}
